<html>
<head>
<title>
GDR: A Visualization Tool for Graph Algorithms
</title>
</head>
<body fgcolor=black bgcolor=white>
<h2>GDR: A Visualization Tool for Graph Algorithms</h2>

<p>
<b>GDR</b> (Graph DRawing) tool
-- developed by Matthias Stallmann, Rance Cleaveland,
and Prashant Hebbar.

<hr>
<h3>&copy;COPYRIGHT</h3>
Matthias Stallmann and Prashant Hebbar; 1989, 2001, 2005, 2007;
version 1.2.9
<p>
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.
<p>
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
<p>
    You should have received a copy of the GNU General Public License along
    with this program (file
    <a href="COPYING.txt">COPYING.txt</a>);
    if not, write to the Free Software
    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
    USA.
<p>
We have the following additional requests:
<ul>
<li>that any publications or software for which this program was useful
give credit by referring to the article "GDR: A Visualization Tool for
Graph Algorithms" by M. Stallmann, R. Cleaveland, and
P. Hebbar in <i>Computational Support for Discrete Mathematics</i> (Dean
and Shannon, editors; AMS, 1994), pp. 17-28;
<li>that any modifications that improve, update, or build upon this program
be reported and made available to us
(
  <code>matt_stallmann AT ncsu.edu</code>).</ul>
<hr>
<strong>New in this version:</strong>
<ul>
  <li> Four new animations: <code>dfs_scc</code> (strongly-connected
  components) supersedes <code>dfs_d</code>, <code>dijkstra</code> (does
  either a minimum spanning tree algorithm or a single-source shortest-paths
  algorithm) supersedes <code>prim.</code>, <code>bfs</code> (breadth-first
       search), and <code>kruskal</code> (Kruskal's minimum spanning tree
       algorithm).  The last two were contributed by Josh Blomberg, CSC 505
       student, Spring 2005.
  </li>
  <li>
  Move mode now works with either the left or middle mouse button (allowing
  operation with a one-button mouse).
  </li>
  <li>
  The pop-up menu can be activated by selecting POP MENU on the panel and
  using the left mouse button (the right button also still works; again, this
  allows operation with a one-button mouse).
  </li>
  <li>
  Keyboard shortcuts for all menu options are displayed on the menu (capital
  letters in parentheses --- the lower-case equivalents also work).
  </li>
  <li>
  A new menu option, <code>RE-(I)NIT</code> allows user to reset the display
  attributes of a graph if an animation fails to clean up after itself
  (labels on vertices and edges are displayed only if they have non-empty
  content -- user needs to decide whether that content needs to be saved).
  </li>
</ul>
<p>
<strong>Known Deficiencies:</strong>
<ul>
  <li>
  Move mode displays only a black dot for the item being moved; cross-hairs
  would be better, but ultimately the display needs to "rubber band" items and
  show their progress (this was too slow when GDR was first developed, but
  should be reasonably fast now).
  </li>
  <li>
  There needs to be a way to cancel a request to read, clear, init, save, or
  quit, with options to save before quitting, etc.  In fact, all the pop-up
  boxes are rather crude by modern standards.
  </li>
</ul>
<hr>

<p><a href="user_doc/index.html">Documentation for the user interface</a>
is available here (slightly outdated -- see the notes about new features
above).

<p><a href="programmer_doc/index.html">Documentation for programmers</a>
(incomplete) is also available.

<p>A "zipped" version of the new code may be downloaded at
<a href="../GDR-1.2.9.zip">
<code>http://courses.ncsu.edu/csc230/common/GDR-1.2.9.zip</code></a>
or copied: the zip file is
<code>/afs/eos/courses/csc/csc230/common/www/GDR-1.2.9.zip.</code>

<p>
Documentation for GDR developers, in the form of a
<a href="html/index.html" >doxygen web site</a> is also
available to help with code browsing.
</p>

<p>
This directory contains files for the GDR graph editing tool and various
animations that have been written.  The file Makefile contains
instructions for compiling all the existing animations (and a list of
the animations themselves).  Source code is contained in files *.[ch].
The *.tex files contain documentation for users of GDR
(programmer_doc.tex is not finished; it attempts to explain how a
programmer can implement other animations on top of GDR).

<p>
The main GDR code is in the following files (a brief description of each
is given):

<p>
<code>All.h</code> 
 -- include this file to get everything needed by any internal GDR module

<p>
<code>Defs.h</code>
 -- data structures, constants, and macros internal to GDR

<p>
<code>Display.h </code>
 -- GDR functions that alter the display of a graph
 
<p>
<code>Gdr.c</code>
 -- implementations of functions required by the GDR programmer and some of their helpers.

<p>
<code>Gdr.h</code>
 -- the file to be included in animation programs using GDR (all other necessary includes emanate from here)

<p>
<code>Geometric.h</code>
 -- GDR functions that access and change geometric attributes

<p>
<code>Globals.h</code>
 -- specifications for global variables used by GDR

<p>
<code>InOut.c</code>
 -- GDR input and output routines

<p>
<code>List.h</code>
 -- routines for manipulating lists of edges
 
<p>
<code>Logical.h</code>
 --  GDR functions accessing and/or manipulating logical graph attributes.

<p>
<code>Macros.h</code>
 --  macros and typedefs for GDR programmers (some of the macros are advertised as functions)

<p>
<code>Main.c</code>
 -- main GDR program and supporting functions

<p>
<code>Misc.h</code>
 -- miscellaneous programmer functions in GDR
 
<p>
<code>Panel.c</code>
 -- routines associated with the side panel (manipulation of the panel itself or functions activated by the panel)

<p>
<code>Prototypes.h</code>
 -- prototypes of functions internal to GDR 

<p>
<code>Settings.h</code>
 -- compile-time constants that can be customized for GDR
 
<p>
<code>Text.c</code>
 -- routines for manipulating text windows

<p>
<code>Utilities.c</code>
 -- routines that perform low-level operations having to do with display or geometry
 
<p>
<code>alphabet.c</code>
 -- functions for manipulating edge labels of graphs representing finite automata

<p>
<code>alphabet.h</code>
 -- header for alphabet.c (functions for manipulating edge labels of graphs that represent finite automata)

<p>
<code>bfs.c</code>
 -- breadth-first search (contributed by Josh Blomberg, CSC 505, Spring 2005)

<p>
<code>bicon.c</code>
 -- biconnectivity algorithm for undirected graphs

<p>
<code>btree.c</code>
 -- a tool for creating binary trees for GDR (the animation draws them
    automatically to fit into a window).

<p>
<code>chk_dfa.c</code>
 -- check a graph to see if it represents a valid dfa

<p>
<code>dfa.c</code>
 -- a DFA simulator
 
<p>
<code>dfs_scc.c</code>
 -- depth-first search for directed graphs, using the
    detailed algorithm of Cormen, Leiserson, and Rivest (Introduction to
    Algorithms, first edition, p. 478).  Also does strongly connected
    components. 

<p>
<code>dijkstra.c</code>
-- Dijkstra's shortest path and minimum spanning tree algorithms (the
   animation asks the user which to do).

<p>
<code>general.h</code>
 -- header file with definitions of general interest, used by the automata
    animations (most of these can be replaced by C constructs and are no
    longer needed).
 
<p>
<code>kruskal.c</code>
 -- Kruskal's minimum spanning tree algorithm
(contributed by Josh Blomberg, CSC 505, Spring 2005)

<p>
<code>minimize.c</code>
 -- DFA minimization algorithm 

<p>
<code>print_logical.c</code>
 -- print logical representation of the graph
 
<p>
<hr>
<p>
Animations that have been implemented so far are (each can be created
using the command <code>make <var>name</var></code>, where <var>name</var>
is listed below):

<dl>
  <dt>bfs
  <dd>breadth-first search of a directed graph; vertex labels show distance
  from the start vertex (contributed by Josh Blomberg, CSC 505, Spring 2005).
    
  <dt>bicon</dt>
  <dd> biconnectivity algorithm for undirected graphs.  DFS always
    starts at vertex 0, vertex labels show preorder and low numbers, edge
    labels show biconnected component to which the edge belongs

  <dt>btree
  <dd>actually not an animation, but the program creates a directed, rooted,
  complete binary tree of a given height
    
  <dt>chk_dfa</dt>
  <dd> a program to check the validity of a DFA (does every state
    have a unique transition for each alphabet symbol)

  <dt>dfa</dt>
  <dd> a DFA simulator.  Vertex 0 is the start state.  Transitions are
    shown by highlighting the transition edge and moving a label containing
    the rest of the string to the new state

  <dt>dfs_scc</dt>
  <dd> Depth-first search on directed graphs, using the description of
    Cormen, Leiserson, and Rivest.  Tree edges are highlighted.  Other edges
    are labeled B, C, or F (back, cross, or forward).  There is also an option
    to find strongly connected components of the graph.
    
  <dt>dijkstra</dt>
  <dd> animates the Dijkstra shortest path algorithm and the
    Prim/Dijkstra minimum spanning tree algorithm (using the
    implementation of Baase).  Edge labels are interpreted as integer costs.
    At each stage, the fringe edges are highlighted as are the tree vertices.
    At the end, all non-tree edges are deleted and the shortest path or minimum
    spanning tree is shown.

  <dt>kruskal</dt>
  <dd>Kruskal's minimum spanning tree algorithm
    (contributed by Josh Blomberg, CSC 505, Spring 2005).

  <dt>minimize</dt>
  <dd> animates the Hopcroft-Ullman O(n log n) algorithm for DFA
    minimization.

  <dt>print_logical</dt>
  <dd> a simple tool to print the logical representation of a
    graph in an easy to read format.

</dl>
<hr>
<address><a href="http://people.engr.ncsu.edu/mfms/">
Matthias Stallmann</a>
(<code>Matt <em>underscore</em> Stallmann <em>at</em> ncsu <em>dot</em> edu</code>)
</address>
<!-- hhmts start -->
Last modified: Thu Jun 28 16:36:54 2007
<!-- hhmts end -->
</body> </html>

<!---
Local Variables: ***
mode:html-helper ***
End: ***
--->
